package 目标和;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/8 11:37
 * @description: 给你一个非负整数数组 nums 和一个整数 target 。
 * 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 * 示例 1：
 * 输入：nums = [1,1,1,1,1], target = 3
 * 输出：5
 * 解释：一共有 5 种方法让最终目标和为 3 。
 * -1 + 1 + 1 + 1 + 1 = 3
 * +1 - 1 + 1 + 1 + 1 = 3
 * +1 + 1 - 1 + 1 + 1 = 3
 * +1 + 1 + 1 - 1 + 1 = 3
 * +1 + 1 + 1 + 1 - 1 = 3
 */
public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // dynamic programming
        // 其实就是找有多少中组合，能够刚好组成 sum / 2 的组合方式，回溯能够解决，但是会超时
        // 采用动态规划解决该问题，寻找最大组合数
        // ① dp数组及其含义：dp[i][j]表示容量为j时，从 0-i 中选择的数字，能够刚好组成 j 的最大组合数
        // ② 动态转移公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]; else dp[i][j] = dp[i - 1][j];
        // ③ dp数组初始化：对于第一行来说，容量为0有一种组合（不挑选任何物品），容量刚好为nums[i]有一种组合方法
        //                对于第一列来说，容量为0都有一种组合方式（不挑选任何物品）
        // ④ 遍历顺序：当前状态的确定，需要上方和左上方的状态进行确定，我们采用先遍历nums，然后在遍历容量
        // ⑤ 举例推导dp数组：nums: [1, 1, 1, 1, 1], target: 3
        //             index    0   1   2   3   4
        //                      1   1   0   0   0
        //                      1   2   1   0   0
        //                      1   3   3   1   0
        //                      1   4   6   4   1
        //                      1   5   10  10  5
        // 如何确定背包容量？
        // 假设加法的总和为 x，那么减法对应的总和就是 sum - x
        //  x - (sum-x) = target  ==>  x = (target + sum) / 2

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (Math.abs(target) > sum || (sum + target) % 2 == 1) return 0;
        int bagSize = (target + sum) / 2;
        // dp
        int[][] dp = new int[nums.length][bagSize + 1];
        // init dp
        dp[0][0] = 1;
        if (bagSize >= nums[0]) {
            dp[0][nums[0]] = 1;
        }

        // 例外,如果物品数值就是0!!!
        // 如果有两个物品，物品0为0， 物品1为0，装满背包容量为0的方法有几种。
        // 放0件物品
        // 放物品0
        // 放物品1
        // 放物品0 和 物品1
        int numZero = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) numZero++;
            dp[i][0] = (int) Math.pow(2, numZero);
        }

        // 状态转移
//        print(dp);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j >= nums[i]) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
//            print(dp);
        }
        return dp[nums.length - 1][bagSize];
    }

    private void print(int[][] dp) {
        for (int i = 0; i < dp.length; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        System.out.println("------------");
    }
}
